package dynamicPlanning;

/**
 * 01 背包
 * 有N件物品和一个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。
 * 每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
 * weight=[1,3,4] value=[15,20,30]
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class Backpack01 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        Solution1 solution1 = new Solution1();
        System.out.println(solution1.backpack());
    }

    /**
     * 1.建立模型，找出dp含义。
     *   dp[i][j]  表示第0~i个物品 装入到容量为j的背包的最大价值
     * 2.找出关系
     *   对于一个物品只可能放或者不放
     *   不放：dp[i][j] = dp[i-1][j]  不放 那么容量不变 物品和上次一致
     *   放： dp[i][j] = dp[i-1][j-wight[i]] + value[i] 即在上一次的基础 容量减去wight[i] 价值增加value[i]
     * 3.初始化
     *   当容量为零，不管有几件物品可以选择，价值都为0  因为装不下; 对于只有一个物品可以选择时，那么
     *   故 dp[0~i][0] = 0 且 dp[0][weight[0]~capacity]=value[0];
     * */
    static class Solution{
        public int backpack(){
            int[] value = {30, 20, 15};
            int[] weight = {4, 3, 1};
            // 背包容量为4 因为背包容量为0的情况是需要考虑到的  所以这里初始化容量背包的时候5
            int capacity = 4;
            int[][] dp = new int[value.length][capacity+1];
            // 初始化 背包容量为0的情况下 装不下物品 价值为0；默认是0 就不做处理了

            // 初始化 当只可以选择第一个物品时
            for(int j = weight[0]; j <= capacity; j++){
                dp[0][j] = value[0];
            }
            // 进入到正式的放和不放流程
            for (int i = 1; i < weight.length; i++) {
                for (int j = 1; j <= capacity; j++) {
                    // 背包容量不够的情况下 就是不放
                    if(j < weight[i]){
                        dp[i][j] = dp[i-1][j];
                    }else{
                        dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);
                    }
                }
            }
            return dp[value.length-1][capacity];
        }
    }

    /**
     * 空间优化版
     * 只需要一维数组
     * dp[j] 表示 背包容量为j时，装下物品最大价值。
     * 我们把i即物品项省略了。为什么可以省略呢?
     * 因为我们从容量最大的开始循环，容量为j时装的最大价值 肯定是 >= 容量为j-1时的最大价值的。
     * */
    static class Solution1{
        public int backpack(){
            int[] value = {30, 20, 15};
            int[] weight = {4, 3, 1};
            // 背包容量为4 因为背包容量为0的情况是需要考虑到的  所以这里初始化容量背包的时候5
            int capacity = 4;
            int[] dp = new int[capacity+1];

            for (int i = 0; i < value.length; i++) {
                for (int j = capacity; j >= weight[i]; j--) {
                    // 容量为j时装的最大价值 肯定是 >= 容量为j-1时的最大价值的 要么不装入第i个物品
                    // 等于容量为j-1时背包的最大价值 要么就是装入i物品 要装入i物品之前，容量为j-weight[i]的价值
                    dp[j] = Math.max(dp[j-1],dp[j-weight[i]] + value[i]);
                }
            }
            return dp[capacity];
        }
    }
}
